/*
 * @lc app=leetcode.cn id=122 lang=swift
 *
 * [122] 买卖股票的最佳时机 II
 */

// @lc code=start
class Solution122 {
    // 贪心解法
    // 因为可以交易多次所以只需要低买高卖就可以了
    // 或者将所有的正利润加起来
    func maxProfit(_ prices: [Int]) -> Int {
        guard prices.count > 1 else {
            return 0
        }
        var sum = 0
        var prePrice = prices[0]
        for i in 1..<prices.count {
            sum += max(prices[i] - prePrice, 0)
            prePrice = prices[i]
        }
        return sum
    }
    // 采用动态规划
    // dp[i][0] 表示不持有股票的剩余的现金
    // dp[i][1] 表示持有股票的剩余的现金
    // 因为可以买卖多次
    func maxProfit0(_ prices: [Int]) -> Int {
        guard prices.count > 0 else {
            return 0
        }
        var dp = Array(repeating: Array(repeating: 0, count: 2), count: prices.count)
        dp[0][0] = 0
        dp[0][1] = -prices[0]
        for i in 1..<prices.count {
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i])
            // 有累加利润 dp[i - 1][0] - prices[i]
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i])
        }
        return dp[prices.count - 1][0]
    }
    static func test() {
        let array = [7,1,5,3,6,4]
        let result = Solution122().maxProfit(array)
        print(result)
    }
}
// @lc code=end

